package 力扣._23_合并K个升序链表;

import 力扣.公用数据结构.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {

    class WListNode {
        ListNode node;
        int index;  //lists数组下标

        public WListNode(ListNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        //优先队列——堆
        ListNode h = new ListNode();
        ListNode r = h;
        PriorityQueue<WListNode> queue = new PriorityQueue<>(new Comparator<WListNode>() {
            @Override
            public int compare(WListNode o1, WListNode o2) {
                return o1.node.val - o2.node.val;  //小在前
            }
        });
        //先进入一轮
        for (int i = 0; i < lists.length; i++) {
            queue.add(new WListNode(lists[i], i));
            lists[i] = lists[i].next;
        }
        while (!queue.isEmpty()) {
            WListNode min = queue.remove();     //取最小
            r.next = min.node;      //插入
            r = min.node;


        }

        return null;
    }
}
